import org.w3c.dom.html.HTMLMapElement;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86136
 * Date: 2024-11-15
 * Time: 21:04
 */
class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val) {
        this.val = val;
    }
}
public class Test {
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int j = i-1;
            int tmp = array[i];
            for (; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    public static void shellSort(int[] array) {
        int gap = array.length;
        while(gap > 1) {
            gap >>= 1;
            shell(array,gap);
        }
    }
    private static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int j = i-gap;
            int tmp = array[i];
            for (; j >= 0 ; j -= gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    array[j+gap] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length-1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            for(int j = left + 1; j <= right; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
                if(array[j] > array[maxIndex]) {
                    maxIndex = j;
                }
            }
            swap(array,left,minIndex);
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

    public static void heapSort(int[] array) {
            createHeap(array);
            int endIndex = array.length - 1;
            while(endIndex > 0) {
                swap(array,0,endIndex);
                siftDown(array,0,endIndex);
                endIndex--;
            }
    }
    private static void createHeap(int[] array) {
        int length = array.length;
        int parent = (length -1 -1)/2;
        for(;parent >= 0;parent--) {
            siftDown(array, parent,length);
        }
    }
    private static void siftDown(int[] array,int parent,int length) {
        int child = parent*2 + 1;
        while(child < length) {
            if(child + 1 < length && array[child+1] > array[child]) {
                child++;
            }
            if(array[parent] < array[child]) {
                //大根堆
                swap(array,parent,child);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                }
            }
        }
    }
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int begin,int end) {
        if(begin >= end) return;
        int pivot = partitionHoare(array,begin,end);
        quick(array,begin,pivot-1);
        quick(array,pivot+1,end);
    }
    private static int partitionHoare(int[] array,int left,int right) {
        int tmpLeft = left;
        while(left < right) {
            while(left < right && array[right] >= array[tmpLeft]) {
                right--;
            }
            while (left < right && array[left] <= array[tmpLeft]) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,tmpLeft,left);
        return left;
    }
    private static void quickSort2(int[] array) {
        quick2(array,0,array.length-1);
    }

    private static void quick2(int[] array, int start, int end) {
        if(start >= end) return;
        int pivot = partition(array,start,end);
        quick2(array,start,pivot-1);
        quick2(array,pivot+1,end);
    }

    private static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while(left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    public static void quickSort3(int[] array) {
        quick3(array,0,array.length-1);
    }

    private static void quick3(int[] array, int start, int end) {
        if(start >= end) return;
        int pivot = partition3(array,start,end);
        quick3(array,start,pivot-1);
        quick3(array,pivot+1,end);
    }

    private static int partition3(int[] array, int left, int right) {
        int prev = left;
        int cur = left+1;
        while(cur <= right) {
            if (array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, prev, cur);
            }
            cur++;
        }
        swap(array,left,prev);
        return prev;
    }

    public static void quickSort4(int[] array) {
        quickNor(array,0,array.length-1);
    }

    private static void quickNor(int[] array, int start, int end) {
        if(end - start + 1 < 3) {
                selectSort4(array);
        }
        int midIndex = findMiddle(start,end);
        swap(array,start,midIndex);
        int pivot = partition4(array,start,end);
        Deque<Integer> stack = new ArrayDeque<>();
        if(start + 1 < pivot) {
            stack.push(start);
            stack.push(pivot-1);
        }
        if(pivot + 1 < end) {
            stack.push(pivot+1);
            stack.push(end);
        }
        while(!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition4(array,start,end);
            if(start+1 < pivot) {
                stack.push(start);
                stack.push(pivot-1);
            }
            if(pivot + 1 < end) {
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

    public static void mergeSort(int[] array) {
        mergeSortTmp(array,0,array.length-1);
    }

    private static void mergeSortTmp(int[] array, int left, int right) {
        if (left >= right) return;
        int mid = left + ((right - left) >> 1);
        mergeSortTmp(array,left,mid);
        mergeSortTmp(array,mid+1,right);
        merge(array,left,mid,right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] tmp = new int[right - left +1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] < array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while(s1 <= e1) {
            tmp[k++] = array[s1++];
        }
        while(s2 <= e2) {
            tmp[k++] = array[s2++];
        }
        for(int i = 0; i < k; i++) {
            array[i+left] = tmp[i];
        }
    }

    private static int partitionHoare2(int[] array, int left, int right) {
        int leftTmp = left;
        while(left < right) {
            while(left < right && array[right] >= array[leftTmp]) {
                right--;
            }
            while(left < right && array[left] <= array[leftTmp]) {
                right++;
            }
            swap(array,left,right);
        }
        swap(array,left,leftTmp);
        return left;
    }

    private static void selectSort4(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    private static int findMiddle( int start, int end) {
        int mid = start + (end -start) >> 2;
        if(start < end) {
            if(mid < start) {
                return start;
            }else if (mid > end) {
                return end;
            }else {
                return mid;
            }
        }else {
            if (mid < end) {
                return end;
            }else if (mid > start) {
                return start;
            }else {
                return mid;
            }
        }
    }

    private static int partition4(int[] array, int left, int right) {
        int tmp = array[left];
        while(left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    public static void mergeSortNor(int[] array) {
        int gap = 1;
        while(gap < array.length) {
            for (int i = 0; i < array.length; i = i + gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                int right = mid + gap;
                if (right >= array.length) {
                    right = array.length - 1;
                }
                merge2(array, left, mid, right);
            }
            gap *= 2;
        }
    }

    private static void merge2(int[] array, int left, int mid, int right) {
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] < array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while(s1 <= e1) {
            tmp[k++] = array[s1++];
        }
        while(s2 <= e2) {
            tmp[k++] = array[s2++];
        }
        for(int i = 0; i < k; i++) {
            array[i+left] = tmp[i];
        }
    }

    public static void countSort(int[] array) {
        //1.遍历数组找到最大值和最小值，做差找到计数数组的长度
        int minVal = array[0];
        int maxVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if(array[i] > maxVal) {
                maxVal = array[i];
            }
        }
        int len = maxVal - minVal + 1;//99 - 90 + 1 = 10
        int[] count = new int[len];
        //2.遍历原数组，把每个元素放入到对应的计数数组中 统计相同元素的个数
        for (int i = 0; i < array.length; i++) {
            int curVal = array[i];
            count[curVal - minVal]++;//94 - 90 = 4
        }
        //3.遍历计数数组，将元素值复原放入原数组中
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while(count[i] > 0) {
                array[index++] = i + minVal;//4 + 90 = 94
                count[i]--;
            }
        }
    }
    public static void main(String[] args) {
        int[] array = {8,7,5,3,6,3,2,5,6,0};
        //insertSort(array);
        //shellSort(array);
        //selectSort(array);
        //heapSort(array);
        //bubbleSort(array);
        //quickSort4(array);
        //mergeSort(array);
        //selectSort2(array);
        //mergeSortNor(array);
        countSort(array);
        for(int num : array) {
            System.out.print(num + " ");
        }
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list0 = new ArrayList<>();
            while(size > 0) {
                TreeNode top = queue.poll();
                list0.add( top.val);
                size--;
                if(top.left != null) {
                    queue.offer(top.left);
                }
                if(top.right != null) {
                    queue.offer(top.right);
                }
            }
            list.add(list0);
        }
        return list;
    }
    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inorder(root);
        }
    }
    public static int i = 0;
    public static TreeNode createTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            i++;
        }
        return root;
    }
    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    public static void main3(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        isSame(str1,str2);
    }
    private static void isSame(String str1,String str2) {
        for(int i = 0; i < str1.length(); i++) {
            int flg = 0;
            char ch1 = str1.charAt(i);
            for(int j = 0; j < str2.length();j++) {
                char ch2 = str2.charAt(j);
                if(ch1 == ch2) {
                    flg = 1;
                }
            }
            if(flg == 0) {
                System.out.print(str1.charAt(i));
            }
        }
    }
}
